<!DOCTYPE html>
<head>
	<title>SAM Visualizer</title>
	<meta charset="UTF-8">
	<script src="./viz.js"></script>
	<script src="//cdn.staticfile.org/jquery/3.3.1/jquery.min.js"></script>
	<script src="//cdn.staticfile.org/semantic-ui/2.3.3/semantic.min.js"></script>
	<link href="//cdn.staticfile.org/semantic-ui/2.3.3/semantic.min.css" rel="stylesheet">
</head>
<style>
</style>
<body>
	<div class="ui main container" style="margin-top: 70px; margin-bottom: 70px;">
		<div class="ui center aligned container" style="width: 100%;">
			<div class="ui form">
				<div class="ui segment stacked">
					<input id="input" placeholder="Strings seperated by vertical bar (|)"/>
					<div style="margin-top: 10px;">
						<button onclick="visualize()" class="ui submit button">Visualize</button>
						<button onclick="rawDot()" class="ui submit basic button">Raw Dot</button>
						<button onclick="countDistinctSubstrings()" class="ui submit basic button">Count Distinct Substrings</button>
					</div>
				</div>
			</div>
		</div>
		<div class="ui center aligned container" style="width: 100%; margin-top: 35px;">
			<div class="ui form">
				<div id="container" class="ui segment stacked" style="display: none;"></div>
			</div>
		</div>
	</div>
</body>
<script>
	var workerURL = "./lite.render.js";
	var viz = new Viz({ workerURL });

	function SAM() {
		this.counter = 0;
		this.son = [ null ];
		this.len = [ null ];
		this.pre = [ null ];
		this.cnt = [ null ];
		this.last = this.create(0);
	}
	SAM.prototype.create = function(len) {
		var x = ++this.counter;
		this.son.push({});
		this.len.push(len);
		this.pre.push(null);
		this.cnt.push(0);
		return x;
	};
	SAM.prototype.extend = function(c) {
		var son = this.son, len = this.len, pre = this.pre;

		var i = this.last;
		var dup = !!son[i][c];
		this.last = dup? son[i][c]: this.create(len[i] + 1);
		while (!son[i][c]) {
			son[i][c] = this.last;
			if (!(i = pre[i])) {
				pre[this.last] = 1;
				return;
			}
		}
		var o = son[i][c];
		if (len[i] + 1 == len[o]) {
			if (dup) this.last = o;
			else pre[this.last] = o;
			return;
		}
		var s = this.create(len[i] + 1);
		son[s] = Object.assign({}, son[o]);
		pre[s] = pre[o];
		pre[o] = s;
		if (dup) this.last = s;
		else pre[this.last] = s;
		do {
			son[i][c] = s;
			i = pre[i];
		} while (i && son[i][c] == o);
	};
	SAM.prototype.finalize = function() {
		var n = this.len[1];
		for (var i = 2; i <= this.counter; ++i)
			if (this.len[i] > n) n = this.len[i];
		var sum = Array(n + 1).fill(0);
		var arr = Array(this.counter + 1);
		for (var i = 1; i <= this.counter; ++i) ++sum[this.len[i]];
		for (var i = 1; i <= n; ++i) sum[i] += sum[i - 1];
		for (var i = 1; i <= this.counter; ++i) arr[sum[this.len[i]]--] = i;
		for (var i = this.counter; i > 1; --i) {
			var x = arr[i];
			this.cnt[this.pre[x]] += this.cnt[x];
		}
	};
	SAM.prototype.toDot = function() {
		var str =
			"digraph {\n" +
			"  1 [color=red];\n";
		for (var i = 1; i <= this.counter; ++i) {
			str += "  " + i + " [label=\"" + i + "\\nlength=" + this.len[i];
			if (i != 1) str += "\\ncount=" + this.cnt[i];
			str += "\"];\n";
			if (this.pre[i])
				str += "  " + i + " -> " + this.pre[i] + " [color=blue];\n";
			for (var key in this.son[i])
				str += "  " + i + " -> " + this.son[i][key] + " [label=\"" + key + "\"];\n";
		}
		str += "}";
		return str;
	};
	SAM.prototype.count = function() {
		var ret = 0;
		for (var i = 2; i <= this.counter; ++i) ret += this.len[i] - this.len[this.pre[i]];
		return ret;
	};

	function buildSAM(arr) {
		var sam = new SAM();
		for (var i = 0; i < arr.length; ++i) {
			var str = arr[i];
			sam.last = 1;
			for (var j = 0; j < str.length; ++j) {
				sam.extend(str[j]);
				++sam.cnt[sam.last];
			}
		}
		sam.finalize();
		return sam;
	}

	var input = document.getElementById("input");
	var container = document.getElementById("container");

	function setContent(element) {
		var old = container.children[0];
		if (old) old.remove();
		container.appendChild(element);
	}

	function get() { return buildSAM(input.value.split("|")); }

	function visualize() {
		document.getElementById('container').style.display = "";
		viz.renderSVGElement(get().toDot())
			.then(function(element) { setContent(element); })
			.catch(error => {
				viz = new Viz({ workerURL });
				alert("Error occurred while rendering: " + String(error));
			});
	}

	function rawDot() {
		document.getElementById('container').style.display = "";
		var element = document.createElement("textarea");
		element.readOnly = "readonly";
		element.value = get().toDot();
		element.style.width = "500px";
		element.style.height = "500px";
		element.style.fontFamily = "monospace";
		setContent(element);
	}

	function countDistinctSubstrings() { alert("Number of distinct substrings: " + get().count()); }
</script>